class Solution
{
public:
    int minSetSize(vector<int> &arr)
    {
        unordered_map<int, int> numFreq;
        for (int num : arr)
        {
            ++numFreq[num];
        }
        vector<vector<int>> freqNum;
        for (auto [num, freq] : numFreq)
        {
            freqNum.push_back({freq, num});
        }
        sort(freqNum.begin(), freqNum.end());
        int n = arr.size();
        int deletedCount = 0;
        int deletedLen = 0;
        for (auto it = freqNum.rbegin(); it != freqNum.rend(); ++it)
        {
            ++deletedCount;
            deletedLen += (*it)[0];
            if (deletedLen * 2 >= n)
            {
                break;
            }
        }
        return deletedCount;
    }
};